package com.ken.algorithms.stack;

import java.util.Stack;

/**
 * <ul>
 * <li>Title: MainLC42</li>
 * <li>Description: TODO </li>
 * </ul>
 *
 * @author 程序员ken
 * @date 2021/5/19 0019 下午 13:57
 */
public class MainLC42 {

    /**
     * 【题目链接】： https://leetcode-cn.com/problems/trapping-rain-water/
     * LeetCode：42. 接雨水 — Hard
     * 【题目描述】：
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
     * 在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     *
     * 【解题思路】：
     * 使用单调递减栈，和 LC84 的思路基本一模一样，甚至都不需要使用哨兵技巧。
     *
     * 当遍历墙的高度的时候，如果当前高度小于栈顶的墙高度，说明这里会有积水，我们将墙的高度的下标入栈。
     * 如果当前高度大于栈顶的墙的高度，说明之前的积水到这里停下，我们可以计算下有多少积水了。
     * 计算完，就把当前的墙继续入栈，作为新的积水的墙。
    */
    public static void main(String[] args) {
        int [] height ={1,2};
                //{0,1,0,2,1,0,1,3,2,1,2,1};

        int water = calWaterVolume(height);

        System.out.println(water);
    }

    private static int calWaterVolume(int[] height) {

        int waterVolume =0;
        Stack<Integer> stack = new Stack<Integer>();

        for (int i = 0; i < height.length; i++) {
            //单调递减  后  面某个大于 当前栈顶的元素  两者中间才能蓄水
            while (!stack.isEmpty() &&  height[i]>height[stack.peek()] ){
                 int cur = stack.pop();
                // 计算以被弹出的栈顶柱子作为底所对应的储水量
                if (stack.isEmpty()) {
                    // 接下来我们需要获取新栈顶的元素，所以此处需要加个判断，保证新栈顶元素存在，否则会报错
                    break;
                }
                int leftIndex  = stack.peek();
                int rightIndex = i;
                int distance  = rightIndex -leftIndex-1;//最大的宽度
                //int curHeight = height[i] - height[leftIndex];
                // 高和度的差值 为蓄水的高度 (错误 应该用栈顶 和 当前值比较 取 最小值 （如木桶短板定律，蓄水量与最短的木板相关))
                int curHeight = Math.min(height[i], height[leftIndex]) - height[cur]; // 水坑的高度  此时减去最低点 才是水坑高度
                waterVolume+= curHeight * distance;
            }
            stack.push(i);
        }
        return waterVolume;
    }


}
